# small comun library of generally useful functions
# by drummyfish, released under CC0 1.0, public domain

# TODO: exp? strfind

# internal library pointers
~_mLibPtrA:0   # tmp pointer
~_mLibPtrB:0   # tmp pointer
~_mLibTmpMem:3 # tiny tmp memory
~_mLibVarA:0   # tmp variable, 2nd cell of tmp memory
~_mLibVarB:0   # tmp variable, 3rd cell of tmp memory

$_mLibTmpMem>_mLibVarA
$>_mLibVarA
$_mLibVarA>_mLibVarB
$>_mLibVarB

# ========== GENERAL ===========================================================

abs: $0 -1 << ? -1 * . . # Absolute value.
min: >' ? >< . ^ .       # Minimum of two values.
max: <' ? >< . ^ .       # Maximum of two vlaues.
minS: >>' ? >< . ^ .     # Minimum of two signed values.
maxS: <<' ? >< . ^ .     # Maximum of two signed values.
min3: min min .          # Minimum of three values.
max3: max max .          # Maximum of three values.

# Interpolates from $3 to $2 by a factor of $1/$0.
lerp:
  $3 $3 > ? # if going from higher to lower, swap
    $3 $3 $:5 $:3
    $0 $2 - $:2
  .

  >< $2 $4 - * >< / >< ^ +
.

# Hashes input number to a 16 bit value, can also be used as a pseudorandom
# generator.
hash:
  $0 +b010000000 * +  +xffff %
  $0 +b100000000 / |! +xffff %
  $0 +b000001000 * +  +xffff %
  $0 +b000000100 / |! +xffff %
  $0 +b000010000 * +  +xffff %
  $0 +b100000000 / |! +xffff %
.

# ========== STRINGS ===========================================================
# String is a sequence of ASCII character codes, considered starting stack top
# and continuing downwards, ending with value 0.

charToUpper:
  $0 "a" >= $1 "z" <= & ? "a" - "A" + .
.

charToLower:
  $0 "A" >= $1 "Z" <= & ? "A" - "a" + .
.

# Converts string to all upper-case.
strToUpper:
  $0>_mLibPtrA

  1 @
    $_mLibPtrA
    $0 charToUpper $:_mLibPtrA
    $<_mLibPtrA
  .
.

# Converts string to all lower-case.
strToLower:
  $0>_mLibPtrA

  1 @
    $_mLibPtrA
    $0 charToLower $:_mLibPtrA
    $<_mLibPtrA
  .
.

# Reads newline-terminated string from input, pushes it as a zero terminated
# string in reversed order, without the newline.
strRead:
  0

  @@
    <-

    $0 10 = ?
      ^ !@
    .
  .

  strReverse
.

# Prints values from memory stack up to stack top.
stackPrint:
  $$ arrayPrint
.

# Computes string length.
strLen:
  $0>_mLibPtrA
  0

  @@
    $_mLibPtrA 0 = ?
      !@
    .

    ++
    $<_mLibPtrA
  .
.

# Expects two strings which won't be popped, pushes 1 if they're equal, else 0.
strEq:
  $0>_mLibPtrA
  $0>_mLibPtrB

  @@
    $_mLibPtrB 0 = ?
      !@
    .

    $<_mLibPtrB
  .

  $<_mLibPtrB

  @@
    $_mLibPtrA $_mLibPtrB != ?
      0 !.
    .

    $_mLibPtrA 0 = ?
      1 !.
    .

    $<_mLibPtrA
    $<_mLibPtrB
  .
.

# Left-pads a string to length $1 with character $0.
strPad:
  $:_mLibVarA
  $:_mLibVarB

  strLen $_mLibVarB >< -

  @@
    $0 0 <<= ?
      ^ !@
    .

    $_mLibVarA ><
    --
  .
.

# Reverses a zero-terminated string.
strReverse:
  strLen arrayReverse ^
.

# ========== MATH ==============================================================

# Power: pops 2, pushes $1 raised to $0.
pow:
  1 ><

  @'
    >< $2 * ><
    --
  .
 
  ^ >< ^ 
.

# Square roots a number using binary search.
sqrt:
  0 $1 2 /  # stack: x lower upper

  @@
    $0 $2 - 1 <= ?
      !@
    .

    $1 $1 + 2 /
    $0 $0 *    # stack: x lower upper middle middle^2

    $4 > ?
      $:1
    ;
      $:2
    .
  .

  $0 $0 * $3 <= ?  
    ><
  .

  ^ >< 1 = +
.

# Computes integer logarithm of $0 with base $1.
log:
  0 # result
  1 # exponentiated value
  1 # previous exponentiated value

  @@
    $1 $4 = ? # equality has to be checked, considering overflow may happen next
      !@
    .

    $2 ++ $:3    # compute next power
    $1 $5 * $:2

    $1 $4 > $2 $2 <= || ? # new power > x or new <= previous (overflow)?
      $2 -- $:3
      !@      
    .

    $1 $:1       # current -> previous
  .

  ^ ^ >< ^ >< ^
.

# Computes 8bit sine function approximation with quadratic curve, value 256 on
# input represents the whole period (2 * pi), output value is between 0 and 255.
sin8:
  $0 256 % 64 / # quadrant
  >< 64 %

  $1 2 % 1 = ?
    63 >< -
  .

  63 - $0 * 32 /

  >< 1 <= ?
    255 >< -
  .
.

# Computes 8bit cosine function approximation.
cos8:
  64 + sin8
.

# Computes factorial recursively.
fact:
  ?'
    $0 -- fact *
  ;
    ^ 1
  .
.

# Checkes if number is a prime.
isPrime:
  $0 1 <=
  ?
    ^ 0 # 0 and 1 are not primes
  ;
    $0 2 /

    @@
      $0 1 <=
      ?
        ^ ^ 1 !.
      .

      $1 $1 % 0 =
      ?
        ^ ^ 0 !.
      .

      --
    .
  .
.

# ========== NUMBER PRINTING AND CONVERSION TO/FROM STRINGS ====================

# Internal function, converts number to base passed in variable A.
_numToStrBase:
  0 ><
  @@
    $0 $_mLibVarA % 

    $0 10 < ? "0" ; "A" 10 - .
    + ><
    $_mLibVarA /

    $0 0 = ?
      !@
    .
  .
  ^
.

numToStrBin: 2 $:_mLibVarA _numToStrBase .
numToStrHex: 16 $:_mLibVarA _numToStrBase .
numToStr: 10 $:_mLibVarA _numToStrBase .

# Converts a signed number to zero-terminated string.
numToStrS:
  $0 0 <<
  ?
    -1 >< - 1 +
    numToStr
    "-"
  ;
    numToStr
  .
.

numPrint: numToStr --> .
numPrintS: numToStrS --> .
numPrintHex: numToStrHex --> .
numPrintBin: numToStrBin --> .

# Converts number from decimal string (zero terminated reverse pushed on stack),
# negative numbers are also supported, validity is not checked.
numFromStr:
  $0 "-" = ?
    ^ numFromStr -1 *
  ;
    0

    @@
      $1 0 = ?
        !@
      .

      10 *

      "0" - +
    .

    >< ^
  .
.

# ========== ARRAYS ============================================================
# Array here means N valus on the stack and the value N pushed afterwards.
# Functions working with arrays normally leave this unchanged without popping,
# e.g. sorting an array will just change orders of the items in the array.

# Prints out given array (from lowest memory address towards stack top).
arrayPrint:
  $0>_mLibPtrA
  $:_mLibVarA'

  @@ # move pointer A to bottom of array
    $_mLibVarA

    ?'
      -- $:_mLibVarA
      $<_mLibPtrA
    ;
      ^ !@
    .
  .

  @@ # now go up and print
    $_mLibPtrA=0 0 = ?
      !@
    .

    $_mLibPtrA numPrint " " ->
    $>_mLibPtrA
  .
.

# Reverses items in given array.
arrayReverse:
  $0>_mLibPtrA
  $:_mLibVarA'

  @@
    $_mLibVarA

    ?'
      -- $:_mLibVarA
      $<_mLibPtrA
    ;
      ^ !@
    .
  .

  $0>_mLibPtrB
  $<_mLibPtrB

  @@
    $_mLibPtrA=_mLibPtrB 2 != ?
      !.
    .

    $_mLibPtrA $_mLibPtrB
    $:_mLibPtrA $:_mLibPtrB

    $>_mLibPtrA
    $<_mLibPtrB
  .
.

# Sorts an array in ascending order (towards stack top) with bubble sort.
arraySort:
  $0 --

  @'
    $0>_mLibPtrA
    $<_mLibPtrA
    $<_mLibPtrA

    $0
    @'
      $_mLibPtrA $<_mLibPtrA $_mLibPtrA

      <' ?
        ><
        $:_mLibPtrA $>_mLibPtrA $:_mLibPtrA $<_mLibPtrA
      ;
        ^ ^
      .

      --
    .

    ^
    --
  .
  ^
.

# Sorts an array in descending order.
arraySortDesc:
  arraySort arrayReverse
.

